package leetcode10;

public class test56 {
    /**
     * 79. 单词搜索
     */
    private static final int[][] DNS = {{0,1},{0,-1},{-1,0},{1,0}};
    public boolean exist(char[][] board, String word) {
        char[] c = word.toCharArray();
        for(int i = 0;i < board.length;i++){
            for(int j = 0;j < board[0].length;j++){
                if(dfs(board,c,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,char[] c,int i,int j,int k){
        if(board[i][j] != c[k]){
            return false;
        }
        if(k == c.length - 1){
            return true;
        }
        board[i][j] = 0;
        for(int[] d:DNS){
            int x = i + d[0];
            int y = j + d[1];
            if(x >= 0 && x < board.length && y >= 0 && y < board[0].length && dfs(board,c,x,y,k + 1)){
                return true;
            }
        }
        board[i][j] = c[k];
        return false;
    }
}
